Conventionally, there is known a method of establishing correspondence between images by searching corresponding points between an input image and a reference image when verifying the input image with a reference image registered beforehand. The input image may be input through an image input apparatus such as a scanner.
For example, in “Computational vision and regularization theory” by T. Poggio, V. Torre and C. Koch, in NATURE Vol. 317, pp. 314-319, 1985 (“conventional art 1”), discloses a technique using the standard regularization theory for minimizing a set energy function in a calculus of variations. In the standard regularization theory adopted in the conventional art 1, corresponding points between images are calculated at minimizing energy by employing a repetition calculation merely using a local information. As a result, parallel distributed process can be performed, and in addition, information processing such as that performed in a human brain may be realized.
“Monotonic and continuous two-dimensional warping method based on a Dynamic Programming ” by Seiichi UCHIDA and Hiroaki SAKOE, in THE TRANSACTIONS OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS D-II, Vol. J81-D-II no. 6, pp. 1251-1258, June 1998 (“conventional art 2”), discloses a technique of a two-dimensional DP-warping method for efficiently searching an optimum solution with DP. According to the conventional art 2, the optimization problem can be solved efficiently.
However, the conventional art 1 has a problem. Because the corresponding points are calculated by minimizing energy with repetition calculation merely using a local information, the solution greatly depends on the initial value. In addition, because it is easy to converge to a local solution, it is difficult to obtain an optimum correspondence.
Further, the conventional art 2 also has a problem. Although an optimum solution can be efficiently searched with DP, amount of calculation becomes vast. Concretely, calculation time having exponent-order for an image size is required in order to obtain the optimum solution.
In view thereof, an important problem occurs how an apparatus is realized which searches corresponding points of images and which can rapidly obtain a result of a stable correspondence without resulting in any local solution when making an image correspond to the other image, i.e. applying correspondence relationship to between images.